import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 八大排序算法
 */
public class SortTest {
    public static void main(String[] args) {
        int[] nums = {3,2,4,1,5};
        sortArray(nums);
        for (int x: nums) {
            System.out.print(x + " ");
        }
    }
    public static int[] sortArray(int[] nums) {
        return heepSort(nums);
    }

    // 数组中的元素交换
    public static void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    // 6. 归并排序
    // 稳定排序算法
    // 时间复杂度：O(NlogN)
    // 空间复杂度：O(N)
    public static int[] mergeSort(int[] nums, int left, int right) {
        if(left >= right) {
            return nums;
        }
        int mid = (right - left) / 2 + left;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int[] tmp = new int[right - left + 1];
        int k = 0;
        int i = left;
        int j = mid + 1;
        while(i <= mid && j <= right) {
            if(nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            }else {
                tmp[k++] = nums[j++];
            }
        }
        while(i <= mid) {
            tmp[k++] = nums[i++];
        }
        while(j <= right) {
            tmp[k++] = nums[j++];
        }
        k = 0;
        for(i = left; i <= right; i++) {
            nums[i] = tmp[k++];
        }
        return nums;
    }

    // 5. 手写堆排序，升序排序
    //   (1) 创建大根堆
    //   (2) 堆首元素和最后一个元素进行交换，排序范围减一
    //   (3) 维护大根堆，重复步骤2，直到范围的元素只剩一个
    // 不稳定的排序算法
    // 时间复杂度：O(NlogN)
    // 空间复杂度：O(1)
    public static int[] heepSort(int[] nums) {
        // 1. 创建大根堆
        //    向上调整
        shiftUp(nums);
        // 2. 堆首元素和最后一个元素交换，并将数组范围减一
        //    再将剩余范围的数组恢复为大根堆，需要向下调整
        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, 0, i);
            shiftDown(nums, 0, i - 1);
        }
        return nums;
    }

    // 向下调整
    private static void shiftDown(int[] nums, int index, int length) {
        int parent = index;
        while (parent * 2 + 1 <= length) {
            int max = 0;
            if(parent * 2 + 2 <= length) {
                if(nums[parent * 2 + 1] < nums[parent * 2 + 2]) {
                    max = parent * 2 + 2;
                }else {
                    max = parent * 2 + 1;
                }
            }else {
                max = parent * 2 + 1;
            }
            if(nums[max] < nums[parent]) {
                break;
            }
            swap(nums, max, parent);
            parent = max;
        }
    }

    // 向上调整
    //       3           3
    //     2   4      1     2
    //   1   5      4   5
    private static void shiftUp(int[] nums) {
        int len = nums.length - 1;
        int node = (len - 1) / 2;
        while(node >= 0) {
            int max = 0;
            if(node * 2 + 1 <= len && node * 2 + 2 <= len) {
                if(nums[node * 2 + 1] > nums[node * 2 + 2]) {
                    max = node * 2 + 1;
                }else {
                    max = node * 2 + 2;
                }
            }else if(node * 2 + 1 <= len) {
                max = node * 2 + 1;
            }
            if(max != 0) {
                if(nums[max] > nums[node]) {
                    swap(nums, max, node);
                    shiftDown(nums, max, len);
                }
            }
            node--;
        }
    }

    // 4. 选择排序
    // 不稳定排序
    // 时间复杂度：O(N ^ 2)
    // 空间复杂度：O(1)
    public static int[] selectSort(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            int min = i;
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[j] < nums[min]) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
        return nums;
    }

    // 3. 冒泡排序
    // 稳定排序
    // 时间复杂度：O(N ^ 2)
    // 空间复杂度：O(1)
    public static int[] swapSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean flg = false;
            for (int j = 0; j < nums.length - i - 1; j++) {
                if(nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    flg = true;
                }
            }
            if(flg == false) {
                break;
            }
        }
        return nums;
    }

    // 2. 插入排序
    // 稳定排序
    // 时间复杂度：O(N ^ 2)
    // 空间复杂度：O(1)
    public static int[] insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int tmp = nums[i];
            int j = i - 1;
            while(j >= 0) {
                if(tmp >= nums[j]) {
                    break;
                }
                swap(nums, j + 1, j);
                j--;
            }
        }
        return nums;
    }

    // 1. 快速排序，挖坑法
    // 不稳定排序
    // 时间复杂度：O(NlogN)
    // 空间复杂度：O(logN)，递归栈
    public static int[] qSort(int[] nums, int left, int right) {
        if(left >= right) {
            return nums;
        }
        int temp = nums[left];
        int i = left;
        int j = right;
        while(i < j) {
            while (i < j && nums[j] >= temp) {
                j--;
            }
            nums[i] = nums[j];
            while(i < j && nums[i] <= temp) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = temp;
        qSort(nums, left, i);
        qSort(nums, i + 1, right);
        return nums;
    }
}
